package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/unique-binary-search-trees/
 *  96. 不同的二叉搜索树 直接递归吧
 * author: hongchen.liao
 * date:  2022/8/28
 */
public class _96_Unique_Binary_Search_Trees {

    class Solution {
        int[][] memo;
        public int numTrees(int n) {
            memo = new int[n+1][n+1];
            return count(1, n);
        }

        int count(int low, int hi){
            if(low > hi) return 1;
            if(memo[low][hi] != 0) return memo[low][hi];
            int res = 0;
            for(int i = low; i <= hi; i++){
                int left = count(low, i-1);
                int right = count(i+1, hi);
                res += left * right;
            }
            memo[low][hi] = res;
            return res;
        }
    }

}
